P5057 简单题

有一个 $n$ 个元素的数组，每个元素初始均为 $0$。有 $m$ 条指令，每条指令为两种操作中的一种：

1. 让其中一段连续序列数字反转；（即 $0$ 变 $1$，$1$ 变 $0$）
2. 询问某个元素的值。

输入格式

第一行包含两个整数 $n,m$，表示数组的长度和指令的条数。

接下来 $m$ 行，每行的第一个数 $t$ 表示操作的种类：

• 若 $t=1$，则接下来有两个数 $L,R$，表示反转区间 $[L,R]$ 的每个数；
• 若 $t=2$，则接下来只有一个数 $i$，表示询问的下标。

输出格式

每个操作 $2$ 输出一行（非 $0$ 即 $1$），表示每次操作 $2$ 的回答。

$1\le n\le {10}^5$，$1\le m\le 5\times {10}^5$，保证 $L\le R$。

Solution

线段树/树状数组 典

同 P2574 XOR的艺术，不过第二个单点查询有点不一样

#define lc u<<1
#define rc u<<1|1
int n, m;
int a[100010];
struct tr { //线段树
    ll l, r, sum, add;
}tr[400010];

void pushup(ll u) { //上传
    tr[u].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(ll u) { //区间XOR的下传
    if (tr[u].add) {
        tr[lc].sum = tr[lc].r - tr[lc].l + 1 - tr[lc].sum;
        tr[rc].sum = tr[rc].r - tr[rc].l + 1 - tr[rc].sum;
        tr[lc].add ^= 1;
        tr[rc].add ^= 1;
        tr[u].add = 0;
    }
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,a[l],0};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
void change(ll u, ll l, ll r) { //区修
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum = (tr[u].r - tr[u].l + 1) - tr[u].sum;
        // tr[u].add += k;
        tr[u].add ^= 1;
        return;
    }
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= m) change(lc, l, r);
    if (r > m) change(rc, l, r);
    pushup(u);
}
ll query(ll u, ll l, ll r, ll x) { //区查
    if (l == r) return tr[u].sum;
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (x <= m) return query(lc, l, m, x);
    else return query(rc, m + 1, r, x);
}
void solve() {
    cin >> n >> m;
    build(1, 1, n);
    while (m--) {
        int op;cin >> op;
        if (op == 1) {
            int l, r;cin >> l >> r;
            change(1, l, r);
        } else {
            int x;
            cin >> x;
            cout << query(1, 1, n, x) << '\n';
        }
    }
}